#include <stdio.h>
#include <stdlib.h>
#include "Espace.h"
#include"Vecteur.h"
#include <assert.h>
#include<time.h>

/* Declarations des structures du graphe internes a ce fichier */

struct Maillon
{
  int info;
  struct Maillon * suiv;
};

typedef struct Maillon maillon, * chain_list;

struct Graph
{
  int nb_sommets;            /* nombre de sommets du graphe                                          */
  int nb_aretes;             /* nombre d'aretes du graphe                                            */
  chain_list * list_voisins; /* ensembles des sommets voisins de chaque sommet (liste d'adjacence)   */
  int ** mat_voisins;        /* ensembles des sommets voisins de chaque sommet (matrice d'adjacence) */
};

typedef struct Graph graph;

/* Fin declarations */

/* Declarations des fonctions internes du module Espaces */
int EstVoisin(vecteur *tab1,vecteur *tab0,int i,int j,int n);
void ajoutSommet(graph *g,vecteur *tab0,vecteur *tab1,int j,int n);
void retraitSommet(graph *g);
void initialeGraphe(graph *g,int n);
int est_acyclique (graph g);
void freeEspace(espace *esp);
void constructionGraphe(graph *g);
/* Fin des declarations */


void InitEspace(espace *esp,int n)
{
  vecteur v1={1,0,0},v2={0,1,0},v3={0,0,1},temp,temp1,temp2,temp3,temp4;
  int i,j,k;
  esp->terrain=(int*)malloc(n*n*n*sizeof(int));
  esp->taille=n;
  for(i=0;i<n;i++)
    {
      produit(&v1, i, &temp1, 0);
      for(j=0;j<n;j++)
	{
	  produit(&v2, j, &temp2, 0);
	  for(k=0;k<n;k++)
	    {
	      produit(&v3, k, &temp3, 0);
	      addition(&temp1,&temp2,&temp4,0);
	      addition(&temp4,&temp3,&temp,0);
	      setCube(esp,&temp,0);
	    }
	}
      
    }
}

int getCube(espace *esp,vecteur *vect)
{
	
	int n;
  assert(getXVecteur(vect)>=0 && getXVecteur(vect)<(esp->taille) && getYVecteur(vect)>=0 && getYVecteur(vect)<(esp->taille) && getZVecteur(vect)>=0 && getZVecteur(vect)<(esp->taille));
	
	n=esp->taille;
	
  return *(esp->terrain+getXVecteur(vect)+getYVecteur(vect)*n+getZVecteur(vect)*n*n);
}

void setCube(espace *esp,vecteur *vect,int valeur)
{
  
	int n;
	n=esp->taille;
	
  assert(getXVecteur(vect)>=0 && getXVecteur(vect)<(esp->taille) && getYVecteur(vect)>=0 && getYVecteur(vect)<(esp->taille) && getZVecteur(vect)>=0 && getZVecteur(vect)<(esp->taille));
  *(esp->terrain+getXVecteur(vect)+getYVecteur(vect)*n+getZVecteur(vect)*n*n)=valeur;
}



void freeEspace(espace *esp)
{
  free(esp->terrain);
}


void initEspaceFichier(espace * esp, vecteur * v, char *pied, char *regard, char fichier[])
{
	FILE *f;
	int i,j,k,n;
	
	
	
	f=fopen(fichier,"r");
	if(f==NULL)
	{
		printf("Erreur d'ouverture  \n");
		assert(f);
	}
	
	n=fgetc(f)-48;
	
	setXVecteur(v,fgetc(f)-48);
	
	setYVecteur(v,fgetc(f)-48);
	
	setZVecteur(v, fgetc(f)-48);
	
	*pied=fgetc(f);
	*regard=fgetc(f);
	
	esp->terrain=(int*)malloc(n*n*n*sizeof(int));
	esp->taille=n;
	
	for(k=0;k<n;k++)
	{
		for(j=0;j<n;j++)
		{
			for(i=0;i<n;i++)
			{
				*(esp->terrain+i+j*n+k*n*n)=fgetc(f)-48;
			}
		}
	}
	fclose(f);
}

void initEspaceAlea(espace *esp,vecteur *position,vecteur *arrivee, int n)
{

  graph g;
  vecteur v1={1,0,0},v2={0,1,0},v3={0,0,1},temp,temp1,temp2,temp3,temp4;
  vecteur *tab0=(vecteur *)malloc(n*n*n*sizeof(vecteur));
  vecteur *tab1=(vecteur *)malloc(n*n*n*sizeof(vecteur));
  int fin;
  int j,k,i,u;
  u=0;
  fin=n*n*n-1;
  InitEspace(esp,n);

  srand(time(NULL)); /* On initialise le rand  à une position aléatoire*/
  
  /* Remplissage de tab0 le tableau des elements candidats (pouvant eventuellment etre transforme en case pleine */

  for(i=0;i<n;i++)
    {
      produit(&v1, i, &temp1, 0);
      for(j=0;j<n;j++)
	{
	  produit(&v2, j, &temp2, 0);
	  for(k=0;k<n;k++)
	    {
	      produit(&v3, k, &temp3, 0);
	      addition(&temp1,&temp2,&temp4,0);
	      addition(&temp4,&temp3,&temp,0);
	      remplaceVecteur(&tab0[u], &temp);
	      u++;
	    }
	}
    }
  /* Initialisation du graphe */
   initialeGraphe(&g,n);

   /* Remplissage de tab1 le tableau des cases pleines */

  while(fin>=0)
    {
      /* On choisit aleatoirement un element de tab0 (tableau des cases vides) */
      
      j=rand()%(fin+1);
      
      /* On ajoute temporairement l element choisi au graphe g */
      /* Puis on teste si g est acyclique */
      /* Si oui on ajoute l element a tab1 */
      /* Si non on retire l element du graphe */
      ajoutSommet(&g,tab0,tab1,j,n);
      if(!est_acyclique (g))
	{
	  retraitSommet(&g);
	}
      else
	{
	  remplaceVecteur(&tab1[(g.nb_sommets)-1], &tab0[j]);
	}
      
      /* Dans les 2 cas l element n est plus candidat */
      /* On le retire de la liste des candidats en le permutant avec le dernier element de tab0 */
      remplaceVecteur(&tab0[j],&tab0[fin]);
      fin--;
    }
  
  /* Maintenant on genere notre espace a partir des elements de tab1 */

  for(i=0;i<g.nb_sommets;i++)
    {
      setCube(esp,&tab1[i],1);
    }
  
  /* maintenant on choisit aleatoirement des elements distincts de tab1 qui vont constituer la position initiale du visiteur (celle des pieds) et la case arrivee */
  i=rand()%g.nb_sommets;
  remplaceVecteur(position, &tab1[i]);
  remplaceVecteur(&tab1[i],&tab1[g.nb_sommets-1]);
  j=rand()%(g.nb_sommets-1);
  remplaceVecteur(arrivee, &tab1[j]);
  setCube(esp,arrivee,9);
  free(tab0);
  free(tab1);

}

void ajoutSommet(graph *g,vecteur *tab0,vecteur *tab1,int j,int n)
{
  int i,k;
  chain_list p;
  p=NULL;
  k=g->nb_sommets++;
  
  /* Ici on ajoute le nouveau sommet en remplissant la liste de ses voisins(au passage on met à jour la liste des voisins de ces voisins) et en mettant à jour la matrice d adjacence du graphe */ 
  for(i=0;i<k;i++)
    {
      if(EstVoisin(tab1,tab0,i,j,n))
	{
	  g->mat_voisins[i][k]=1;
	  g->mat_voisins[k][i]=1;
	  p=(chain_list)malloc(sizeof(maillon));
	  p->info=k;
	  p->suiv=g->list_voisins[i];
	  g->list_voisins[i]=p;
	  p=(chain_list)malloc(sizeof(maillon));
	  p->info=i;
	  p->suiv=g->list_voisins[k];
	  g->list_voisins[k]=p;
	  g->nb_aretes++;
	}
    }
}
	  
  
void retraitSommet(graph *g)
{
  chain_list p;
  int k;
  int i;
  p=NULL;
  k=g->nb_sommets;

  /* Ici on retire le dernier element ajoute au graphe en mettant à jour la liste des voisins de ses voisins et la matrice d'adjacence */
  for(i=0;i<k;i++)
    {
      if(g->mat_voisins[i][k]==1)
	{
	  g->mat_voisins[i][k]=0;
	  g->mat_voisins[k][i]=0;
	  p=g->list_voisins[i];
	  g->list_voisins[i]=p->suiv;
	  free(p);
	  p=g->list_voisins[k];
	  g->list_voisins[k]=p->suiv;
	  free(p);
	  g->nb_aretes--;
	}
    }
  g->nb_sommets--;
}

void initialeGraphe(graph *g,int n)
{
  int i,j;
  g->nb_sommets=0;
  g->nb_aretes=0;
  /* Initialisation du graphe qui peut contenir potentiellement n*n*n sommets */
  /* Et chaque sommet peut avoir jusqu a n*n*n-1 voisins */
  g->list_voisins=(chain_list *)malloc(sizeof(chain_list)*n*n*n);
  g->mat_voisins=(int **)malloc(sizeof(int*)*n*n*n);
  for(i=0;i<n*n*n;i++)
    {
      g->mat_voisins[i]=(int *)malloc(sizeof(int)*n*n*n);
      g->list_voisins[i]=NULL;
      
      /* Matrice d adjacence est mis a 0 */ 
      for(j=0;j<n*n*n;j++)
	{
	  g->mat_voisins[i][j]=0;
	}
    }
}

int EstVoisin(vecteur *tab1,vecteur *tab0,int i,int j,int n)
{
  vecteur v1={1,0,0},v2={0,1,0},v3={0,0,1},v4={1,1,0},v5={1,0,1},v6={0,1,1};
  vecteur v7={-1,0,0},v8={0,-1,0},v9={0,0,-1},v10={1,-1,0},v11={-1,1,0},v12={1,0,-1};
  vecteur v13={-1,0,1},v14={0,1,-1},v15={0,-1,1},v16={-1,-1,0},v17={-1,0,-1},v18={0,-1,-1};
  vecteur v;
  soustraction(&tab0[j], &tab1[i], &v, n);

  if(compareVecteur(&v,&v1)||compareVecteur(&v,&v2)||compareVecteur(&v,&v3)||compareVecteur(&v,&v4)||compareVecteur(&v,&v5)||
     compareVecteur(&v,&v6)||compareVecteur(&v,&v7)||compareVecteur(&v,&v8)||compareVecteur(&v,&v9)||compareVecteur(&v,&v10)||
     compareVecteur(&v,&v11)||compareVecteur(&v,&v12)||compareVecteur(&v,&v13)||compareVecteur(&v,&v14)||compareVecteur(&v,&v15)||
     compareVecteur(&v,&v16)||compareVecteur(&v,&v17)||compareVecteur(&v,&v18))
    {
      return 1;
    }
  else
    {
      return 0;
    }
  
  
}

int est_acyclique (graph g)
/* Renvoie 1 si le graphe g est acyclique, 0 sinon */
{
  int nb_var, nb_aretes;
  int * marque,nb_marque;
  int * pile, sommet;
  chain_list ls;
  int v;
  int comp_conn=0;

  if (g.nb_aretes <= g.nb_sommets - 1)
  {
    marque = (int *) malloc (sizeof(int) * g.nb_sommets);
    pile = (int *) malloc (sizeof(int) * g.nb_sommets);

    nb_marque = 0;
    for (v = 0; v < g.nb_sommets; v++)
      if (g.list_voisins[v] == NULL)
      {
        marque[v] = 1;
	nb_marque++;
	comp_conn++;
      }
      else marque[v] = 0;

    sommet = 0;

    while (nb_marque != g.nb_sommets)
    {
      /* parcours d'une composante connexe */
      nb_var = 0;
      nb_aretes = 0;
      comp_conn++;

      /* Recherche du premier sommet de la composante connexe courante */      
      v = 0;
      while (marque[v]) v++;

      marque[v] = 1;
      nb_marque++;

      pile[sommet++] = v;

      while (sommet != 0)
      {
        v = pile[--sommet];
	nb_var++;

        ls = g.list_voisins[v];
        while (ls != NULL)
        {
          if (! marque[ls->info])
          {
            pile[sommet++] = ls->info;
            marque[ls->info] = 1;
            nb_marque++;
          }
	  nb_aretes++;
          ls = ls->suiv;
        }
      }
      
      /* Teste si la composante connexe est un arbre */
      if (nb_aretes % 2 != 0) printf ("Erreur");
      nb_aretes = nb_aretes / 2;
      if (nb_aretes != nb_var - 1)
      {
        free (pile);
        free (marque);

        return 0;
      }
    }

    free (pile);
    free (marque);

    return (1);
  }
  else return 0;
}
